package main.java.indi.zyj.hot100;

public class _59_canPartition {

    public boolean canPartition(int[] nums) {

        int len = nums.length;

        if (len == 0 || nums == null) return false;

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if ((sum & 1) == 1){
            return false;
        }

        int target = sum / 2;
        int[] dp = new int[target + 1];

        for (int i = 0; i < len; i++) {
            for (int j = target; j >= nums[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;
    }

}
